package com.hot100.easy;

/**
 * @ClassName Demo04
 * @Description 最大子串和
 * @Author zt
 * @Date 15:29 2022/6/8
 * @Version 1.0
 * 给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
  子数组 是数组中的一个连续部分
 **/
public class Demo04 {
    public static void main(String[] args) {
        int[] nums={1,1,1};
        System.out.println(maxSubArray2(nums));
    }

    public  static int maxSubArray(int[] nums) {
       int max=Integer.MIN_VALUE;
        for (int i = 0; i < nums.length; i++) {
            int temp=nums[i];
            if(max<temp){
                max=temp;
            }
            for (int j = i+1; j <nums.length ; j++) {
                temp=temp+nums[j];
                if(max<temp){
                    max=temp;
                }
            }
        }
        return max;
    }
    /**
     * 方法一超时了
     */
    public  static int maxSubArray2(int[] nums) {
       int[] newNums=new int[nums.length];
       newNums[0]=nums[0];
       int max=nums[0];
        for (int i = 1; i <nums.length; i++) {
            newNums[i]=Math.max(newNums[i-1]+nums[i],nums[i]);
            max=Math.max(max,newNums[i]);
        }
        return max;
    }
}